home *** CD-ROM | disk | FTP | other *** search
/ Aminet 7 / Aminet 7 - August 1995.iso / Aminet / dev / misc / VSort.lha / vsort.c < prev    next >
C/C++ Source or Header  |  1995-04-19  |  11KB  |  506 lines
  1. /******************************************************************************
  2. **                                                                           **
  3. ** VSort V 1.0                                                               **
  4. **                                                                           **
  5. *******************************************************************************
  6. ** Visualisierung von Sortierprozessen                                       **
  7. ** by Stefan Kost                                                            **
  8. ** 19.04.1995                                                                **
  9. ******************************************************************************/
  10.  
  11. #include "sc:source/vsort/vsort.h"
  12.  
  13. /* Protos */
  14.  
  15. void gen_tdat(void);
  16. void draw_tdat(void);
  17. void swap(UWORD i1,UWORD i2);
  18.  
  19. void BubbleSort(void);
  20. void SelectionSort(void);
  21. void InsertionSort(void);
  22. void ShellSort(void);
  23. void QuickSort(UWORD l,UWORD r);
  24. void MergeSort(UWORD l,UWORD r);
  25. void RadixExchangeSort(UWORD l,UWORD r,WORD b);
  26. UWORD bits(UWORD x,UWORD k);
  27. void HeapSort(void);
  28. void downheap(UWORD n,UWORD k);
  29.  
  30. void Message(char *title,char *text);
  31. UBYTE Question(char *title,char *text);
  32.  
  33. void Wait1(void);
  34. void Wait2(void);
  35.  
  36. void OpenAll(void);
  37. void CloseAll(void);
  38.  
  39. /* globale Var`s */
  40.  
  41. UWORD tdat[maxanz],tmp[maxanz];
  42. UBYTE sortmode=0,datamode=1,delayt=0;
  43. UWORD swapct=100,anz=100;
  44.  
  45. char *strbuf="          ";
  46. ULONG tempvar;
  47. char *tempstr;
  48.  
  49. /*============================================================================*/
  50.  
  51. void gen_tdat(void)
  52. {
  53.     register UWORD i;
  54.  
  55.     switch(datamode)
  56.     {
  57.         case 0:
  58.             for(i=0;i<anz;i++) tdat[i]=i;
  59.             break;
  60.         case 1:
  61.             for(i=0;i<anz;i++) tdat[i]=i;
  62.             for(i=0;i<swapct;i++) swap(rand()%anz,rand()%anz);
  63.             break;
  64.         case 2:
  65.             for(i=1;i<=anz;i++) tdat[i]=anz-i;
  66.             break;
  67.         case 3:
  68.             for(i=1;i<=anz;i++) tdat[i]=anz-i;
  69.             for(i=0;i<swapct;i++) swap(rand()%anz,rand()%anz);
  70.             break;
  71.     }
  72. }
  73.  
  74. void draw_tdat(void)
  75. {
  76.     register UWORD i;
  77.  
  78.     SetAPen(&rp,1);
  79.     WaitTOF();SetRast(&rp,0);
  80.     WaitTOF();for(i=0;i<anz;i++) WritePixel(&rp,i,anz-tdat[i]);
  81. }
  82.  
  83. void swap(UWORD i1,UWORD i2)
  84. {
  85.     UWORD tmp;
  86.  
  87.     tmp=tdat[i1];tdat[i1]=tdat[i2];tdat[i2]=tmp;
  88. }
  89.  
  90. /*============================================================================*/
  91.  
  92. void BubbleSort(void)
  93. {
  94.     register UWORD i,j;
  95.  
  96.     for(i=0;i<anz;i++)
  97.     {
  98.         for(j=0;j<(anz-1);j++)
  99.         {
  100.             if(tdat[j]>tdat[j+1]) swap(j,j+1);
  101.         }
  102.         draw_tdat();Delay(delayt);
  103.     }
  104. }
  105.  
  106. void SelectionSort(void)
  107. {
  108.     register UWORD i,j,mp;
  109.  
  110.     for(i=0;i<anz;i++)
  111.     {
  112.         mp=i;
  113.         for(j=i;j<anz;j++)
  114.         {
  115.             if(tdat[j]<tdat[mp]) mp=j;
  116.         }
  117.         swap(i,mp);
  118.         draw_tdat();Delay(delayt);
  119.     }
  120. }
  121.  
  122. void InsertionSort(void)
  123. {
  124.     register UWORD i,mp;
  125.  
  126.     for(i=1;i<anz;i++)
  127.     {
  128.         mp=i;
  129.         while(mp>0 && tdat[mp]<tdat[mp-1])
  130.         {
  131.             swap(mp,mp-1);mp--;
  132.         }
  133.         draw_tdat();Delay(delayt);
  134.     }
  135. }
  136.  
  137. void ShellSort(void)
  138. {
  139.     register UWORD i,h=1,mp;
  140.  
  141.     while(h<=(anz/9)) h=3*h+1;
  142.     while(h)
  143.     {
  144.         for(i=h;i<=anz;i++)
  145.         {
  146.             mp=i;
  147.             while(mp!=h-1 && tdat[mp]<tdat[mp-h])
  148.             {
  149.                 swap(mp,mp-h);mp--;
  150.             }
  151.             draw_tdat();Delay(delayt);
  152.         }
  153.         h=h/3;
  154.     }
  155. }
  156.  
  157. void QuickSort(UWORD l,UWORD r)
  158. {
  159.     register UWORD v,i,j;
  160.  
  161.     if(r>l)
  162.     {
  163.         v=tdat[r];i=l-1;j=r;
  164.         for(;;)
  165.         {
  166.             while(tdat[++i]<v);
  167.             while(tdat[--j]>v);
  168.             if(i>=j) break;
  169.             swap(i,j);
  170.             draw_tdat();Delay(delayt);
  171.         }
  172.         swap(i,r);
  173.         draw_tdat();Delay(delayt);
  174.         QuickSort(l,i-1);
  175.         QuickSort(i+1,r);
  176.     }
  177. }
  178.  
  179. void MergeSort(UWORD l,UWORD r)
  180. {
  181.     register UWORD i,j,k,m;
  182.  
  183.     if(r>l)
  184.     {
  185.         m=(r+l)>>1;                                                                /* Mitte bilden */
  186.         draw_tdat();Delay(delayt);
  187.         MergeSort(l,m);                                                            /* Teilfolgen sortieren */
  188.         MergeSort(m+1,r);
  189.         for(i=m+1;i>l;i--) tmp[i-1]=tdat[i-1];                                    /* in Hilfsfeld übertragen */
  190.         for(j=m;j<r;j++) tmp[r+m-j]=tdat[j+1];
  191.         for(k=l;k<=r;k++) tdat[k]=(tmp[i]<tmp[j]) ? tmp[i++] : tmp[j--];        /* und zusammenmischen */
  192.         draw_tdat();
  193.     }
  194. }
  195.  
  196. void RadixExchangeSort(UWORD l,UWORD r,WORD b)
  197. {
  198.     register UWORD i,j;
  199.  
  200.     if(r>l && b>=0)
  201.     {
  202.         i=l;j=r;
  203.         while(j!=i)
  204.         {
  205.             while(!bits(tdat[i],b) && i<j) i++;
  206.             while(bits(tdat[j],b) && j>i) j--;
  207.             swap(i,j);
  208.             draw_tdat();Delay(delayt);
  209.         }
  210.         if(!bits(tdat[r],b)) j++;
  211.         RadixExchangeSort(l,j-1,b-1);
  212.         RadixExchangeSort(j,r,b-1);
  213.     }
  214. }
  215.  
  216. UWORD bits(UWORD x,UWORD k)
  217. {
  218.     return((UWORD)((x>>k)&~(~0<<1)));
  219. }
  220.  
  221. void HeapSort(void)
  222. {
  223.     register UWORD k,n=anz-1;
  224.  
  225.     for(k=(n>>1);k>=0;k--) downheap(n,k);
  226.     draw_tdat();Delay(delayt);
  227.     while(n)
  228.     {
  229.         swap(0,n);
  230.         downheap(--n,0);
  231.         draw_tdat();Delay(delayt);
  232.     }
  233. }
  234.  
  235. void downheap(UWORD n,UWORD k)
  236. {
  237.     register UWORD j,v;
  238.  
  239.     v=tdat[k];
  240.     while(k<=(n>>1))
  241.     {
  242.         j=k+k;
  243.         if(j<n && tdat[j]<tdat[j+1]) j++;
  244.         if(v>=tdat[j]) break;
  245.         tdat[k]=tdat[j];k=j;
  246.     }
  247.     tdat[k]=v;
  248. }
  249.  
  250. /*============================================================================*/
  251.  
  252. void Message(char *title,char *text)
  253. {
  254.     MUI_RequestA(app1,0,0,title,"_Okay",text,NULL);
  255. }
  256.  
  257. UBYTE Question(char *title,char *text)
  258. {
  259.     return((UBYTE)MUI_RequestA(app1,0,0,title,"_Okay|_Cancel",text,NULL));
  260. }
  261.  
  262. /*============================================================================*/
  263.  
  264. void Wait1(void)
  265. {
  266.     struct IntuiMessage *imsg;
  267.     ULONG iclass;
  268.     USHORT icode;
  269.     UBYTE quit=0;
  270.  
  271.     while(!quit)
  272.     {
  273.         WaitPort(gfxwin->UserPort);
  274.         while(imsg=GetMsg(gfxwin->UserPort))
  275.         {
  276.             iclass    =imsg->Class;
  277.             icode    =imsg->Code;
  278.             ReplyMsg(imsg);
  279.             switch(iclass)
  280.             {
  281.                 case IDCMP_RAWKEY:
  282.                     switch(icode)
  283.                     {
  284.                         case 0x40:        /* Space */
  285.                         case 0x43:        /* Enter */
  286.                         case 0x44:        /* Return */
  287.                             quit=1;break;
  288.                     }
  289.                     break;
  290.             }
  291.         }
  292.     }
  293. }
  294.  
  295. void Wait2(void)
  296. {
  297.     struct IntuiMessage *imsg;
  298.     ULONG iclass;
  299.     USHORT icode;
  300.     UBYTE quit=0;
  301.  
  302.     while(!quit)
  303.     {
  304.         WaitPort(gfxwin->UserPort);
  305.         while(imsg=GetMsg(gfxwin->UserPort))
  306.         {
  307.             iclass    =imsg->Class;
  308.             icode    =imsg->Code;
  309.             ReplyMsg(imsg);
  310.             switch(iclass)
  311.             {
  312.                 case IDCMP_RAWKEY:
  313.                     switch(icode)
  314.                     {
  315.                         case 0x40:        /* Space */
  316.                         case 0x43:        /* Enter */
  317.                         case 0x44:        /* Return */
  318.                         case 0x45:        /* ESC */
  319.                             quit=1;break;
  320.                     }
  321.                     break;
  322.                 case IDCMP_CLOSEWINDOW:
  323.                     quit=1;break;
  324.             }
  325.         }
  326.     }
  327. }
  328.  
  329. /*============================================================================*/
  330.  
  331. void OpenAll(void)
  332. {
  333.     srand(time(NULL));
  334. }
  335.  
  336. void CloseAll(void)
  337. {
  338.     if(main_win)    set(main_win,MUIA_Window_Open,FALSE);
  339.     fail(app1,NULL);
  340. }
  341.  
  342. /*============================================================================*/
  343.  
  344. int main(int argc,char *argv[])
  345. {
  346.     ULONG signals=0l;
  347.     BOOL running=TRUE;
  348.  
  349.     init();
  350.     OpenAll();
  351.  
  352.     app1 = ApplicationObject,
  353.         MUIA_Application_Title,            "VisualSort",
  354.         MUIA_Application_Version,        "$VER: VisualSort 1.0 (19.04.95)",
  355.         MUIA_Application_Copyright,        "by Stefan Kost ©1995,",
  356.         MUIA_Application_Author,        "Stefan Kost",
  357.         MUIA_Application_Description,    "Visualisierung von Sortierprozessen",
  358.         MUIA_Application_Base,            "VSORT",
  359.  
  360.         SubWindow, main_win = WindowObject,
  361.             MUIA_Window_Title, "VisualSort V1.0",
  362.             MUIA_Window_ID   , MAKE_ID('S','O','M','A'),
  363.  
  364.             WindowContents,VGroup,
  365.                 Child, HGroup,GroupFrameT("Settings"),
  366.                     Child, VGroup,
  367.                         Child, Label2("Sorttyp"),
  368.                                 Child, Label2("Datatyp"),
  369.                         Child, Label2("Swapct."),
  370.                         Child, Label2("   Size"),
  371.                         Child, Label2("  Delay"),
  372.                     End,
  373.                     Child, VGroup,
  374.                         Child, main_sorttyp = CycleObject,
  375.                             MUIA_Cycle_Entries,sorttyp,
  376.                             MUIA_Cycle_Active,ST_BUBBLE,
  377.                         End,
  378.                         Child, main_datatyp = CycleObject,
  379.                             MUIA_Cycle_Entries,datatyp,
  380.                             MUIA_Cycle_Active,DT_MERGED,
  381.                         End,
  382.                         Child, main_swapct = StringObject,StringFrame,End,
  383.                         Child, main_anz = StringObject,StringFrame,End,
  384.                         Child, main_delay = StringObject,StringFrame,End,
  385.                     End,
  386.                 End,
  387.                 Child, HGroup,GroupFrameT("Control"),
  388.                     Child, main_go = SimpleButton("Go"),
  389.                     Child, main_exit = SimpleButton("Exit"),
  390.                     Child, main_about = SimpleButton("About"),
  391.                 End,
  392.             End,
  393.         End,
  394.     End;
  395.  
  396.     if(!app1) CloseAll();
  397.  
  398. /*
  399. ** Install notification events...
  400. */
  401.  
  402.     DoMethod(main_win,        MUIM_Notify,MUIA_Window_CloseRequest,TRUE,            app1,2,    MUIM_Application_ReturnID,ID_EXIT);
  403.  
  404.     DoMethod(main_go,        MUIM_Notify,MUIA_Pressed,FALSE,                        app1,2,    MUIM_Application_ReturnID,ID_GO);
  405.     DoMethod(main_exit,        MUIM_Notify,MUIA_Pressed,FALSE,                        app1,2,    MUIM_Application_ReturnID,ID_EXIT);
  406.     DoMethod(main_about,    MUIM_Notify,MUIA_Pressed,FALSE,                        app1,2,    MUIM_Application_ReturnID,ID_ABOUT);
  407.  
  408.     DoMethod(main_sorttyp,    MUIM_Notify,MUIA_Cycle_Active,MUIV_EveryTime,         app1,2, MUIM_Application_ReturnID,ID_SORTTYP);
  409.     DoMethod(main_datatyp,    MUIM_Notify,MUIA_Cycle_Active,MUIV_EveryTime,         app1,2, MUIM_Application_ReturnID,ID_DATATYP);
  410.     DoMethod(main_swapct,    MUIM_Notify,MUIA_String_Acknowledge,MUIV_EveryTime,    app1,2, MUIM_Application_ReturnID,ID_SWAPCT);
  411.     DoMethod(main_anz,        MUIM_Notify,MUIA_String_Acknowledge,MUIV_EveryTime,    app1,2, MUIM_Application_ReturnID,ID_ANZ);
  412.     DoMethod(main_delay,    MUIM_Notify,MUIA_String_Acknowledge,MUIV_EveryTime,    app1,2, MUIM_Application_ReturnID,ID_DELAY);
  413.  
  414.     sprintf(strbuf,"%d",anz);    set(main_anz,MUIA_String_Contents,strbuf);
  415.     sprintf(strbuf,"%d",swapct);set(main_swapct,MUIA_String_Contents,strbuf);
  416.     sprintf(strbuf,"%d",delayt);set(main_delay,MUIA_String_Contents,strbuf);
  417.  
  418.     set(main_win,MUIA_Window_Open,TRUE);
  419. /*
  420. ** Cycle chain for keyboard control
  421. */
  422.     while(running)
  423.     {
  424.         switch(DoMethod(app1,MUIM_Application_Input,&signals))
  425.         {
  426.             case MUIV_Application_ReturnID_Quit:
  427.                 running=FALSE;
  428.                 break;
  429.             case ID_EXIT:
  430.                 if(Question("Exit ?",ques[0])) running=FALSE;
  431.                 break;
  432.             case ID_GO:
  433.                 if(scr=LockPubScreen(0l))
  434.                 {
  435.                     wintags[2].ti_Data=anz;
  436.                     wintags[3].ti_Data=anz;
  437.                     wintags[7].ti_Data=scr;
  438.                     if(gfxwin=OpenWindowTagList(0l,wintags))
  439.                     {
  440.                         set(main_win,MUIA_Window_Sleep,TRUE);
  441.                         rp=*gfxwin->RPort;
  442.                         gen_tdat();draw_tdat();Wait1();
  443.                         switch(sortmode)
  444.                         {
  445.                             case 0: BubbleSort();break;
  446.                             case 1: SelectionSort();break;
  447.                             case 2: InsertionSort();break;
  448.                             case 3: ShellSort();break;
  449.                             case 4: QuickSort(0,anz-1);break;
  450.                             case 5: MergeSort(0,anz-1);break;
  451.                             case 6: RadixExchangeSort(0,anz-1,16);break;
  452.                             case 7: HeapSort();break;
  453.                         }
  454.                         Wait2();
  455.                         set(main_win,MUIA_Window_Sleep,FALSE);
  456.                         CloseWindow(gfxwin);
  457.                     }
  458.                     UnlockPubScreen(0l,scr);
  459.                 }
  460.                 break;
  461.             case ID_ABOUT:
  462.                 Message("About",mess[0]);
  463.                 break;
  464.  
  465.             case ID_SORTTYP:
  466.                 get(main_sorttyp,MUIA_Cycle_Active,&tempvar);sortmode=(UBYTE)tempvar;
  467.                 break;
  468.             case ID_DATATYP:
  469.                 get(main_datatyp,MUIA_Cycle_Active,&tempvar);datamode=(UBYTE)tempvar;
  470.                 switch(datamode)
  471.                 {
  472.                     case 0:    set(main_swapct,MUIA_Disabled,TRUE);break;
  473.                     case 1:    set(main_swapct,MUIA_Disabled,FALSE);break;
  474.                     case 2:    set(main_swapct,MUIA_Disabled,TRUE);break;
  475.                     case 3:    set(main_swapct,MUIA_Disabled,FALSE);break;
  476.                 }
  477.                 break;
  478.             case ID_SWAPCT:
  479.                 get(main_swapct,MUIA_String_Contents,&tempstr);
  480.                 swapct=atoi(tempstr);
  481.                 break;
  482.             case ID_ANZ:
  483.                 get(main_anz,MUIA_String_Contents,&tempstr);
  484.                 anz=atoi(tempstr);
  485.                 if(anz>maxanz)
  486.                 {
  487.                     anz=maxanz;sprintf(strbuf,"%d",anz);
  488.                     set(main_anz,MUIA_String_Contents,strbuf);
  489.                 }
  490.                 break;
  491.             case ID_DELAY:
  492.                 get(main_delay,MUIA_String_Contents,&tempstr);
  493.                 tempvar=atoi(tempstr);
  494.                 if(tempvar>255)
  495.                 {
  496.                     delayt=255;sprintf(strbuf,"%d",delayt);
  497.                     set(main_delay,MUIA_String_Contents,strbuf);
  498.                 }
  499.                 else delayt=(UBYTE)tempvar;
  500.                 break;
  501.         }
  502.         if(running && signals) Wait(signals);
  503.     }
  504.     CloseAll();
  505. }
  506.